package com.pan.alg.basic.sortbasic;

import org.apache.commons.lang3.ArrayUtils;

public class BinaryInsertSort {

    /**
     * 二分法排序<br>
     * 根据排序原则，每次我们都是在一个有序序列中插入一个新的数字<br>
     * 那么我们可以将这个有序序列进行二分。<br>
     * 左游标left为0，右游标right为i-1(i是这个数字在原数组中的位置)<br>
     * middle初始为。<br>
     * 当left<=right时<br>
     * middle是left和right的中值。<br>
     * 我们作如下操作。如果array[i]的值比array[middle]值大。<br>
     * 那么我们就移动左游标令值为middle+1<br>
     * 负责就移动右游标为middle-1<br>
     * 移动完成后,我们需要将i-1到left之间的值进行依次向后移动给array[i]空出一个位置然后将array[i]插入
     * <p style="color:red">时间复杂度n</p>
     */
    public static int[] binaryInsertSort(int[] array) {

        for (int i = 0; i < array.length; i++) {
            //待插入到前面有序序列的值
            int temp = array[i];
            //有序序列的左侧
            int left = 0;
            //有序序列的右侧
            int right = i;
            //有序序列的中间
            int middle = 0;
            while (left < right) {

                middle = (left + right) / 2;
                if (temp < array[middle]) {
                    right = middle;
                }else if(temp == array[middle]){
                    right = middle;
                    break;
                }
                else{
                    left = middle + 1;
                }
            }
            for (int j = i; j > right; j--) {
                //从i-1到left依次向后移动一位,等待temp值插入
                array[j] = array[j-1];
            }
            array[right] = temp;

        }
        return array;
    }

  public static void main(String[] args) {
    //
      int[] arr ={4,3,6,7,8,9,4,2,11,23,56,43,45};
       binaryInsertSort(arr);
      System.out.println(ArrayUtils.toString(arr));
  }
}
